package uba.algo3.tp2.ej1;

import java.util.PriorityQueue;
import java.util.Collection;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.HashMap;

public class PriorityQueueExt<E> extends PriorityQueue {
	
	/* representacion interna del min-heap, donde se cumple que si i es un nodo, entonces
	 * sus hijos estan en las posiciones 2i+1 y 2i+2 */
	private ArrayList<Ciudad> arrayHeap = new ArrayList<Ciudad>();
	/* indice de cada Ciudad en arrayHeap, para poder obtener desde Maximo.java una ciudad
	 * en tiempo constante */
	private HashMap<Ciudad,Integer> indiceEnHeap = new HashMap<Ciudad,Integer>();
	
	/* Al crear el PriorityQueueExt, sabemos que la ciudad origen es la raiz del heap (con prioridad 
	 * infinito), y todos los demas tienen prioridad 0 */
	PriorityQueueExt(Collection<Ciudad> cc){ //O(V*logV)
		super(cc); //O(V*logV)
		pasarAArrayHeap(cc); //O(V)
		buildMinHeapify(); //O(V*logV)
		llenarIndiceEnArrayHeap(); //O(V)
	}
	
	private void pasarAArrayHeap(Collection<Ciudad> cc){
		Iterator<Ciudad> it = cc.iterator();
		int i=0;
		while(it.hasNext()){
			arrayHeap.add(it.next());
			i++;
		}
	}
	
	private void buildMinHeapify(){ //REVISARLO BIEN AL FINAL!!!
		for (int i = (arrayHeap.size())/2 - 1; i >= 0; i--) {
			minHeapify(i);
		}  
	}
	
	private void minHeapify(int i){
		minHeapifyAux(i);
	}
	
	private void minHeapifyAux(int i) {
		int l = 2 * i + 1;
		int r =  2 * i + 2;
		int largest = -1;
		
		if (l < arrayHeap.size() && arrayHeap.get(l).compareTo(arrayHeap.get(i)) < 0 )
			largest = l;
		else
			largest = i;
		
		if (r < arrayHeap.size() && arrayHeap.get(r).compareTo(arrayHeap.get(largest)) < 0 )
			largest = r;
		
		if (largest != i) {
			swap(arrayHeap,i,largest);
			minHeapifyAux(largest);
		}
	}
	
	private void llenarIndiceEnArrayHeap(){
		for(int i=0; i<arrayHeap.size(); i++){
			indiceEnHeap.put(arrayHeap.get(i), i);
		}
	}
	
	public Ciudad poll(){
		Ciudad max = (Ciudad) super.poll(); //O(logV)
		desencolar(); //O(logV)
		return max;
	}
	
	private void desencolar(){
		int n = arrayHeap.size();
		indiceEnHeap.remove(arrayHeap.get(0));
		Ciudad ultimaHoja = arrayHeap.get(n-1);
		indiceEnHeap.put(ultimaHoja, 0);
		arrayHeap.set(0, ultimaHoja);
		arrayHeap.remove(n-1);
		bajar(0); //baja el nodo raiz hasta reestablecer el invariante
	}
	
	private void bajar(int nodeIndex) {
		int n = arrayHeap.size();
        int leftChildIndex, rightChildIndex, minIndex;
        leftChildIndex = 2*nodeIndex + 1;
        rightChildIndex = 2*nodeIndex + 2;
        if (rightChildIndex >= n) {
              if (leftChildIndex >= n)
                    return;
              else
                    minIndex = leftChildIndex;
        } else {
              if (arrayHeap.get(leftChildIndex).compareTo(arrayHeap.get(rightChildIndex)) > 0)
                    minIndex = leftChildIndex;
              else
                    minIndex = rightChildIndex;
        }
        if (arrayHeap.get(nodeIndex).compareTo(arrayHeap.get(minIndex)) > 0) {
        	//actualizo en indiceEnHeap
        	Ciudad uno = arrayHeap.get(nodeIndex);
        	Ciudad dos = arrayHeap.get(minIndex);
        	indiceEnHeap.put(uno,minIndex);
        	indiceEnHeap.put(dos,nodeIndex);
        	//actualizo en arrayHeap
        	swap(arrayHeap,nodeIndex,minIndex);
            bajar(minIndex);
        }
    }
	
	public void incrementarPrioridad(String ciudad, int pesoNuevo){
		/**
		 * Reordena (si es necesario) la ciudad pasada como parametro en el heap, cambiandole
		 * su prioridad (su pesoHastaAqui)
		 */
		int posEnArrayHeap = indiceEnHeap.get(ciudad);
		arrayHeap.get(posEnArrayHeap).cambiarPesoHastaAqui(pesoNuevo); //le cambio la prioridad
		subir(posEnArrayHeap);	
	}
	
	private void subir(int nodeIndex){
		int indiceActual = nodeIndex;
		int indicePadre;
		while(indiceActual!=0){ //mientras el indice actual no sea la raiz
			if(indiceActual % 2 != 0) //si es hijo izquierdo
				indicePadre = (indiceActual-1)/2;
			else //si es hijo derecho
				indicePadre = (indiceActual-2)/2;
			if(arrayHeap.get(indiceActual).compareTo(arrayHeap.get(indicePadre)) < 0){
				//intercambio posiciones de padre e hijo en indiceEnHeap
			  	Ciudad hija = arrayHeap.get(indiceActual);
	        	Ciudad padre = arrayHeap.get(indicePadre);
	        	indiceEnHeap.put(hija,indicePadre);
	        	indiceEnHeap.put(padre,indiceActual);
				//y tambien en arrayHeap
				swap(arrayHeap,indiceActual,indicePadre);
				//ahora el indice actual es el indice del padre
				indiceActual = indicePadre;
			}else{
				break; //ya esta restituido el invariante del min-heap
			}
		}
	}

	public void mostrarArrayHeap(){
		for(int i=0; i<arrayHeap.size(); i++){
			System.out.print(arrayHeap.get(i) + ",");
		}
		System.out.println();
	}
	
	private void swap(ArrayList<Ciudad> A, int i, int j){
		Ciudad temp = A.get(i);  
        A.set(i,A.get(j));
        A.set(j,temp);
	}
	
}
